﻿#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <memory.h>

using namespace std;

/*
https://www.papamelon.com/problem/361


有 N 个农场，我们要选择修某些路，将所有农场连起来，也就是从任意一个农场都可以去到另一个农场。
给定我们一个N×N 的邻接矩阵，Aij表示农场 i 和 j 之间的道路长度，另外保证 Aij=Aji
求一个最优的修路方案，使得所有农场连接起来的道路总长度最短。

输入
多组测试数据，以 EOF 结束
每组测试数据格式如下：
第一行N(3≤N≤100)，表示农场数量
接下来一个N×N 的矩阵，表示两个农场之间的道路长度
保证 Aii​=0,Aij =Aji
​
保证多组测试数据的 NN 总和不超过 100100
输出
每组测试数据输出一行，一个整数，表示道路最短总长度
样例 1
输入
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
输出
28

*/

const int N = 150;
int gra[N][N];
int n;
int dist[N];
bool st[N];
const int INF = 0x3f3f3f3f;


int prim()
{
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);

	int res = 0;
	for (int i = 0; i < n; i++)
	{
		int t = -1;
		for (int j = 0; j < n; j++)
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;

		if (i && dist[t] == INF) return INF;

		if (i) res += dist[t];
		st[t] = true;

		for (int j = 0; j < n; j++) dist[j] = min(dist[j], gra[t][j]);
	}

	return res;
}


int main()
{
	while (~scanf("%d", &n)) {
		memset(gra,0x3f,sizeof gra);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d",&gra[i][j]);
			}
		}
 
		int t = prim();

		printf("%d\n", t);	
	}

	return 0;
}

 